#include <iostream>
#include <algorithm>
using namespace std;
#define N 3  // 物品的数量
#define C 16 // 背包的容量
// 下面的数组从1开始使用，用-1给下标是0的位置占上，-1没有意义。
int w[N + 1] = {-1, 10, 8, 5}; // 每个物品的重量
int v[N + 1] = {-1, 5, 4, 1};  // 每个物品的价值
int x[N + 1] = {-1, 0, 0, 0};  // 解，但不一定是最优解，x[i]=1代表物品i放入背包，0代表不放入
int CurWeight = 0;             // 当前放入背包的物品总重量
int CurValue = 0;              // 当前放入背包的物品总价值
int BestValue = 0;             // 最优值；当前的最大价值，初始化为0
int BestX[N + 1];              // 最优解；BestX[i]=1代表物品i放入背包，0代表不放入

int bound(int t) // 上界函数，求t物品对应节点的上界限
{
    int cleft = C - CurWeight;
    int b = CurValue; // b存当前节点的上界限
    while (t <= N && w[t] <= cleft)
    {
        cleft = cleft - w[t]; // 物品t放入背包，背包剩余容量减少
        b = b + v[t];         // 物品t放入背包，上界限增加
        t++;
    }
    // 物品已经按照单位重量价值从大到小排序，当前物品不能完全放入背包时
    if (t <= N)//将当前物品在背包中能够贡献的最大价值加入到当前节点的上界限b中
        b = b + v[t] * cleft / w[t];
    return b;//返回传入的t值对应节点的上界限
}

void backtrack(int t)
{
    if (t > N)//检查是否搜索到了叶子节点
    {
        if (CurValue > BestValue)
        {//根据当前的解更新最优解，并返回上一级
            BestValue = CurValue;
            for (int i = 1; i <= N; ++i)
                BestX[i] = x[i];
        }
    }
    else
    {
        // 左子树
        if ((CurWeight + w[t]) <= C)
        {
            x[t] = 1;//标记当前物品放入
            CurWeight += w[t];//当前物品放入背包，进入左子树
            CurValue += v[t];
            backtrack(t + 1);//进入下一层（下一个物品）
            CurWeight -= w[t];//回溯回来后
            CurValue -= v[t];//当前物品不放入背包，进入右子树
        }
        // 右子树
        // bound(t + 1)求的是当前节点不放入时当前节点的上界限
        // 剪枝函数，判断当前节点的下层节点是否需要进一步搜索
        if (bound(t + 1) > BestValue) // 考虑上界函数时增加的代码
        {
            x[t] = 0;//标记当前物品不放入
            backtrack(t + 1);//进入下一层（下一个物品）
        }
    }
}

void sort(int *w, int *v, int n)
{
    int i, j, temp;
    for (i = 1; i < n; i++)
        for (j = 1; j < n - 1 - i; j++)
        {
            if (v[i] / w[i] < v[i + 1] / w[i + 1])
            {
                temp = w[i];
                w[i] = w[i + 1];
                w[i + 1] = temp;

                temp = v[i];
                v[i] = v[i + 1];
                v[i + 1] = temp;
            }
        }
}


int main()
{
    sort(w, v, N); // 依物品单位重量价值排序
    backtrack(1);// 从第一层开始搜索
    cout << "最优值(价值总和最大):" << BestValue << endl;
    cout << "最优解(放入的物品):";
    for (int i = 1; i <= N; i++)
    {
        if(BestX[i])
        cout << "物品" << i << " ";
    }
    return 0;
}
